A packet-switching telecommunication network, relatively new in the field of data transmission, basically consists of a network of queues. The central design problem is the routing of messages in order to minimize the average delay of packets in the queues, taking into account variations in traffic over time and potential sources of failure. An examination of the problem is provided by A. Artom in the article "Problems and Outlook of Packet-switching Telecommunications" published in Elettronica e Telecomunicazioni No. 5, 1976, pages 195-201.
Known methods of routing messages or packets generally rely on an analysis of the state of the system, which in turn includes inspection of queue lengths and an estimation of the incremental delay at each queue with respect to hypothetical infinitesimal variations in traffic flow, as described by A. Segall in an article entitled "The Modeling of Adaptive Routing in Data-Communication Networks" published in IEEE Transactions on Communications, Vol. COM-25, No. 1, January 1977, pages 85-94. The estimation may be used either by the individual nodes, in conjunction with information received from adjacent nodes, or by a centralized supervising node or unit for updating routing tables stored at the nodes. An example of a distributed method for updating routing tables is described by R. Gallager in an article entitled "A Minimum Delay Routing Algorithm Using Distributed Computation" published in the same issue of IEEE Transactions on Communications, pages 73-84.
Conventional methods of estimating incremental delays are generally unsatisfactory, owing to the rapid escalation of operations with increasing packet flow. Thus, backup becomes very difficult to eliminate once it has arisen. Another disadvantage of these known methods is the complexity involved therein, which results in increased costs of the devices implementing the methods and in increased congestion due to the necessity of transmitting greater amounts of information.